The present invention relates generally to database queries and more specifically to aggregate queries.
The design of database query languages has started to benefit from advances in general programming language design. For example, SQL, a common query language, has adopted more referential transparency and compositionality, especially in the versions used for object-relational databases. In addition, a rich and challenging standard language, OQL, has been proposed for object-oriented databases.
As demands for information have become more complex, and as the sizes of databases has increased, queries have become correspondingly complex. Traditional query language compilers directly translate queries written in source language into query execution plans that are then executes against the databases of interest. Doing so often creates plans that consume massive amounts of memory and occupy large amounts of I/O resources. Also, complex queries often require construction of intermediate data structures, which further consumes memory.
The increasing sizes of many databases have made many queries unfeasible without some sort of optimization. Although most compilers for general-purpose programming languages perform some optimizing, they do not generally perform such optimizing for database queries. Moreover, these optimizations are not sound if programs are allowed to diverge or have side-effects. In addition, although some database query language compilers perform optimization, they do not do so for aggregates or conversions, two important functions described in detail below.